package main

/**
 * 二分查找
 */
type MyCalendar struct {
	books [][]int
}

func Constructor() MyCalendar {
	return MyCalendar{[][]int{}}
}

func (this *MyCalendar) Book(start int, end int) bool {
	if len(this.books) == 0 {
		this.books = append(this.books, []int{start, end})
		return true
	}
	left, right := 0, len(this.books)-1

	for left <= right {
		mid := (left + right) >> 1
		if this.books[mid][0] >= end {
			right = mid - 1
		} else if this.books[mid][1] <= start {
			left = mid + 1
		} else {
			return false
		}
	}
	if left == len(this.books) {
		this.books = append(this.books, []int{start, end})
	} else {
		this.books = append(this.books, []int{})
		copy(this.books[left+1:], this.books[left:])
		this.books[left] = []int{start, end}
	}
	// this.books = append(this.books[:left], append([][]int{{start, end}}, this.books[left:]...)...)
	return true
}
